Embodiments of the present invention relate to fast multiplication of operands, at least one of which may be very large.
In a traditional combinatorial multiplier, each bit position in a multiplier is multiplied against a multiplicand to generate an interstitial product. The interstitial product is summed with those from all other bit positions in the multiplier, each shifted so that the least significant bit coincides with the multiplier bit position from which the interstitial product originated, to generate a product.
In many applications, operands to a multiplication operation may be large binary numbers. For example, as part of the negotiations conducted during encrypted transactions, it is common to multiply operands of 1024 or 2048 bits. Multiplication typically involves a shift of a multiplier value A for each bit position of a multiplicand B and possibly an addition with a previously obtained interstitial product. Thus, for a multiplicand of length n, this involves n shifts and as many as n additions. For an extremely long multiplicand (1024 or 2048 bits), the bit-by-bit shifting operations is computationally expensive.
There is a need in the art for a fast multiplication technique for use with long operands. Further, there is a need for such a multiplication technique to be performed without the bit-by-bit processing of prior designs that is so expensive.